//在英语中，我们有一个叫做 词根(root) 的概念，可以词根后面添加其他一些词组成另一个较长的单词——我们称这个词为 继承词(successor)。例如，词
//根an，跟随着单词 other(其他)，可以形成新的单词 another(另一个)。 
//
// 现在，给定一个由许多词根组成的词典 dictionary 和一个用空格分隔单词形成的句子 sentence。你需要将句子中的所有继承词用词根替换掉。如果继
//承词有许多可以形成它的词根，则用最短的词根替换它。 
//
// 你需要输出替换之后的句子。 
//
// 
//
// 示例 1： 
//
// 
//输入：dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by 
//the battery"
//输出："the cat was rat by the bat"
// 
//
// 示例 2： 
//
// 
//输入：dictionary = ["a","b","c"], sentence = "aadsfasf absbs bbab cadsfafs"
//输出："a a b c"
// 
//
// 
//
// 提示： 
//
// 
// 1 <= dictionary.length <= 1000 
// 1 <= dictionary[i].length <= 100 
// dictionary[i] 仅由小写字母组成。 
// 1 <= sentence.length <= 10^6 
// sentence 仅由小写字母和空格组成。 
// sentence 中单词的总量在范围 [1, 1000] 内。 
// sentence 中每个单词的长度在范围 [1, 1000] 内。 
// sentence 中单词之间由一个空格隔开。 
// sentence 没有前导或尾随空格。 
// 
//
// 
// Related Topics字典树 | 数组 | 哈希表 | 字符串 
//
// 👍 245, 👎 0 
//
//
//
//

package leetcode.editor.cn;


import java.util.LinkedList;
import java.util.List;

class ReplaceWords {
    public static void main(String[] args) {
        Solution solution = new ReplaceWords().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public String replaceWords(List<String> dictionary, String sentence) {
            TrieSet set = new TrieSet();
            for (String s : dictionary) {
                set.add(s);
            }

            String[] words = sentence.split(" ");
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < words.length; i++) {
                String prefix = set.shortestPrefixOf(words[i]);
                if (!prefix.isEmpty()) {
                    sb.append(prefix);
                } else {
                    sb.append(words[i]);
                }

                if (i != words.length - 1) {
                    sb.append(" ");
                }
            }

            return sb.toString();
        }

        // 前缀树模板
        // 参照labuladong：https://mp.weixin.qq.com/s/hGrTUmM1zusPZZ0nA9aaNw
        class TrieSet {
            private final TrieMap<Object> map = new TrieMap<>();


            /***** 增 *****/

            // 在集合中添加元素 key
            public void add(String key) {
                map.put(key, new Object());
            }

            /***** 删 *****/

            // 从集合中删除元素 key
            public void remove(String key) {
                map.remove(key);
            }

            /***** 查 *****/

            // 判断元素 key 是否存在集合中
            public boolean contains(String key) {
                return map.containsKey(key);
            }

            // 在集合中寻找 query 的最短前缀
            public String shortestPrefixOf(String query) {
                return map.shortestPrefixOf(query);
            }

            // 在集合中寻找 query 的最长前缀
            public String longestPrefixOf(String query) {
                return map.longestPrefixOf(query);
            }

            // 在集合中搜索前缀为 prefix 的所有元素
            public List<String> keysWithPrefix(String prefix) {
                return map.keysWithPrefix(prefix);
            }

            // 判断集合中是否存在前缀为 prefix 的元素
            public boolean hasKeyWithPrefix(String prefix) {
                return map.hasKeyWithPrefix(prefix);
            }

            // 通配符 . 匹配任意字符，返回集合中匹配 pattern 的所有元素
            public List<String> keysWithPattern(String pattern) {
                return map.keysWithPattern(pattern);
            }

            // 通配符 . 匹配任意字符，判断集合中是否存在匹配 pattern 的元素
            public boolean hasKeyWithPattern(String pattern) {
                return map.hasKeyWithPattern(pattern);
            }

            // 返回集合中元素的个数
            public int size() {
                return map.size();
            }

        }

        class TrieMap<V> {
            // ASCII 码个数
            private static final int R = 256;
            // 当前存在 Map 中的键值对个数
            private int size = 0;
            // Trie 树的根节点
            private TrieNode<V> root = null;

            private class TrieNode<V> {
                V val = null;
                TrieNode<V>[] children = new TrieNode[R];
            }

            // 从节点 node 开始搜索 key，如果存在返回对应节点，否则返回 null
            private TrieNode<V> getNode(TrieNode<V> node, String key) {
                TrieNode<V> p = node;
                // 从节点 node 开始搜索 key
                for (int i = 0; i < key.length(); i++) {
                    // 无法向下搜索
                    if (p == null) {
                        return null;
                    }
                    // 向下搜索
                    p = p.children[key.charAt(i)];
                }
                return p;
            }

            /***** 增/改 *****/

            // 在 Map 中添加 key
            public void put(String key, V val) {
                if (containsKey(key)) {
                    size++;
                }
                root = put(root, key, val, 0);
            }

            public TrieNode<V> put(TrieNode<V> node, String key, V val, int i) {
                if (node == null) {
                    // 如果树枝不存在，新建
                    node = new TrieNode<>();
                }

                if (i == key.length()) {
                    // key 的路径已插入完成，将值 val 存入节点
                    node.val = val;
                    return node;
                }

                char c = key.charAt(i);
                // 递归插入子节点，并接收返回值
                node.children[c] = put(node.children[c], key, val, i + 1);
                return node;
            }

            /***** 删 *****/

            // 删除键 key 以及对应的值
            public void remove(String key) {
                if (!containsKey(key)) {
                    return;
                }
                // 递归修改数据结构要接收函数的返回值
                root = remove(root, key, 0);
                size--;
            }

            // 定义：在以 node 为根的 Trie 树中删除 key[i..]，返回删除后的根节点
            public TrieNode<V> remove(TrieNode<V> node, String key, int i) {
                if (node == null) {
                    return null;
                }

                if (i == key.length()) {
                    // 找到了 key 对应的 TrieNode，删除 val
                    node.val = null;
                } else {
                    char c = key.charAt(i);
                    // 递归去子树进行删除
                    node.children[c] = remove(node.children[c], key, i + 1);
                }

                // 后序位置，递归路径上的节点可能需要被清理
                if (node.val != null) {
                    // 如果该 TireNode 存储着 val，不需要被清理
                    return node;
                }

                // 检查该 TrieNode 是否还有后缀
                for (char c = 0; c < R; c++) {
                    if (node.children[c] != null) {
                        return node;
                    }
                }

                // 既没有存储 val，也没有后缀树枝，则该节点需要被清理
                return null;
            }

            /***** 查 *****/

            // 搜索 key 对应的值，不存在则返回 null
            // get("the") -> 4
            // get("tha") -> null
            public V get(String key) {
                // 从 root 开始搜索 key
                TrieNode<V> node = getNode(root, key);
                if (node == null || node.val == null) {
                    // x 为空或 x 的 val 字段为空都说明 key 没有对应的值
                    return null;
                }
                return node.val;
            }

            // 判断 key 是否存在在 Map 中
            // containsKey("tea") -> false
            // containsKey("team") -> true
            public boolean containsKey(String key) {
                return get(key) != null;
            }

            // 在 Map 的所有键中搜索 query 的最短前缀
            // shortestPrefixOf("themxyz") -> "the"
            public String shortestPrefixOf(String query) {
                TrieNode<V> p = root;
                // 从节点 node 开始搜索 key
                for (int i = 0; i < query.length(); i++) {
                    // 无法向下搜索
                    if (p == null) {
                        return "";
                    }

                    if (p.val != null) {
                        // 找到一个键是 query 的前缀
                        return query.substring(0, i);
                    }

                    p = p.children[query.charAt(i)];
                }

                // 判断是否是一个字符
                if (p != null && p.val != null) {
                    // 如果 query 本身就是一个键
                    return query;
                }

                return "";
            }

            // 在 Map 的所有键中搜索 query 的最长前缀
            // longestPrefixOf("themxyz") -> "them"
            public String longestPrefixOf(String query) {
                TrieNode<V> p = root;
                int maxLen = 0;
                // 从节点 node 开始搜索 key
                for (int i = 0; i < query.length(); i++) {
                    // 无法向下搜索
                    if (p == null) {
                        break;
                    }

                    if (p.val != null) {
                        // 找到一个键是 query 的前缀，更新前缀的最大长度
                        maxLen = i;
                    }

                    p = p.children[query.charAt(i)];
                }

                // 判断是否是一个字符
                if (p != null && p.val != null) {
                    // 如果 query 本身就是一个键
                    return query;
                }

                return query.substring(0, maxLen);
            }

            // 搜索所有前缀为 prefix 的键
            // keysWithPrefix("th") -> ["that", "the", "them"]
            public List<String> keysWithPrefix(String prefix) {
                List<String> res = new LinkedList<>();
                // 找到匹配 prefix 在 Trie 树中的那个节点
                TrieNode<V> node = getNode(root, prefix);

                if (node != null) {
                    return res;
                }

                // DFS 遍历以 x 为根的这棵 Trie 树
                traversal1(node, new StringBuilder(), res);
                return res;
            }

            // 遍历以 node 节点为根的 Trie 树，找到所有键
            public void traversal1(TrieNode<V> node, StringBuilder sb, List<String> path) {
                // 到达 Trie 树底部叶子结点
                if (node == null) {
                    return;
                }

                if (node.val != null) {
                    // 找到一个 key，添加到结果列表中
                    path.add(sb.toString());
                }

                for (char c = 0; c < R; c++) {
                    sb.append(c);
                    traversal1(node.children[c], sb, path);
                    sb.deleteCharAt(sb.length() - 1);
                }
            }

            // 判断是和否存在前缀为 prefix 的键
            // hasKeyWithPrefix("tha") -> true
            // hasKeyWithPrefix("apple") -> false
            public boolean hasKeyWithPrefix(String prefix) {
                // 只要能找到 prefix 对应的节点，就是存在前缀
                return getNode(root, prefix) != null;
            }

            // 通配符 . 匹配任意字符，搜索所有匹配的键
            // keysWithPattern("t.a.") -> ["team", "that"]
            public List<String> keysWithPattern(String pattern) {
                List<String> res = new LinkedList<>();
                traversal2(root, new StringBuilder(), res, pattern, 0);
                return res;
            }

            public void traversal2(TrieNode<V> node, StringBuilder sb, List<String> path, String pattern, int i) {
                if (node == null) {
                    return;
                }

                if (i == pattern.length()) {
                    // pattern 匹配完成
                    if (node.val != null) {
                        // 如果这个节点存储着 val，则找到一个匹配的键
                        path.add(sb.toString());
                    }
                    return;
                }

                char c = pattern.charAt(i);
                if (c == '.') {
                    for (char j = 0; j < R; j++) {
                        sb.append(j);
                        traversal2(node.children[j], sb, path, pattern, i + 1);
                        sb.deleteCharAt(sb.length() - 1);
                    }
                } else {
                    sb.append(node.val);
                    traversal2(node.children[c], sb, path, pattern, i + 1);
                    sb.deleteCharAt(sb.length() - 1);
                }
            }

            // 通配符 . 匹配任意字符，判断是否存在匹配的键
            // hasKeyWithPattern(".ip") -> true
            // hasKeyWithPattern(".i") -> false
            public boolean hasKeyWithPattern(String pattern) {
                // 直接调用复杂度过高，求出了所以匹配的
                // return !keysWithPattern(pattern).isEmpty();
                return hasKeyWithPattern(root, pattern, 0);
            }

            // 函数定义：从 node 节点开始匹配 pattern[i..]，返回是否成功匹配
            private boolean hasKeyWithPattern(TrieNode<V> node, String pattern, int i) {
                // 树枝不存在，即匹配失败
                if (node == null) {
                    return false;
                }

                // 模式串走到头了，看看匹配到的是否是一个键
                if (i == pattern.length()) {
                    return node.val != null;
                }

                char c = pattern.charAt(i);
                if (c == '.') {
                    for (char j = 0; j < R; j++) {
                        // pattern[i] 可以变化成任意字符，尝试所有可能，只要遇到一个匹配成功就返回
                        if (hasKeyWithPattern(node.children[j], pattern, i + 1)) {
                            return true;
                        }
                    }
                } else {
                    // 从 node.children[c] 节点开始匹配 pattern[i+1..]
                    hasKeyWithPattern(node.children[c], pattern, i + 1);
                }

                return false;
            }

            // 返回 Map 中键值对的数量
            public int size() {
                return size;
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
